package com.tyrone.algorithm.graph;

import com.tyrone.algorithm.linear.Queue;

public class BreadthFirstSearch {

    private boolean[] marked;           // 索引代表顶点，值表示当前顶点是否已经被搜索
    private int count;                  //记录有多少个顶点与s顶点相通
    private Queue<Integer> waitSearch;           // 用来存储待搜索邻接表的点

    public BreadthFirstSearch(Graph g,int s) {
        marked = new boolean[g.V()];
        waitSearch=new Queue<Integer>();
        bfs(g,s);
    }

    /**
     * 使用广度优先搜索找出G图中v顶点的所有相邻顶点
     * @param g
     * @param v
     */
    private void bfs(Graph g, int v){
        marked[v]=true;
        waitSearch.enqueue(v);
        while(!waitSearch.isEmpty()){
            Integer dequeue = waitSearch.dequeue();
            for (Integer integer : g.adj(dequeue)) {
                if (!marked[integer]){
                    marked[integer]=true;
                    waitSearch.enqueue(integer);
                    count++;
                    System.out.println(integer);
                }
            }

        }

    }

    /**
     * 判断w顶点与s顶点是否相通
     * @param w
     * @return
     */
    public boolean marked(int w){
        return  marked[w];
    }

    /**
     * 获取与顶点s相通的所有顶点的总数
     * @return
     */
    public int count(){
        return count;
    }
}
